/*
 * @lc app=leetcode.cn id=473 lang=cpp
 *
 * [473] 火柴拼正方形
 */

// @lc code=start
class Solution {
public:
    bool backtrack(int idx, vector<int> &matchsticks, vector<int> &sides) {
        if (idx == -1) return true;
        for (int i = 0; i < 4; i++) {
            if (sides[i] < matchsticks[idx]) continue;
            if (sides[i] == matchsticks[idx] ||
                sides[i] >= matchsticks[idx] + matchsticks[0]) {
                sides[i] -= matchsticks[idx];
                if (backtrack(idx - 1, matchsticks, sides)) return true;
                sides[i] += matchsticks[idx];
            }
        }
        return false;
    }
    bool makesquare(vector<int> &matchsticks) {
        int n = matchsticks.size(), sum = 0;

        for (auto x : matchsticks) {
            sum += x;
        }
        if (sum % 4 != 0) return false;

        vector<int> sides(4, sum / 4);
        sort(matchsticks.begin(), matchsticks.end());

        return backtrack(n - 1, matchsticks, sides);
    }
};
// @lc code=end
